\newpage
\subsubsection{Parallelisierung des Algorithmus} \label{sec:Parallelisierung des Algorithmus} $\;$ \\
Wie bereits in früheren Kapiteln erwähnt ist GZIP in der Programmiersprache C geschrieben und daher nicht unbedingt sehr einfach zu parallelisieren. Das Problem besteht im Besonderen darin, dass viele globale Variablen, Arrays und Buffer verwendet wurden.
\begin{wrapfigure}{l}{0.45\textwidth}
  \begin{center}
    \includegraphics[width=0.3\textwidth]{images/gzip_eclipse_project}
  \end{center}
   \caption[GZIP Sourcecode Struktur]{GZIP Sourcecode Struktur}
   \label{fig:gzip_source}
\end{wrapfigure}
Außerdem ist GZIP ein einigermaßen komplexes Programm, so dass auch erfahrene Entwickler einige Zeit benötigen um den Programmablauf nachzuvollziehen und zu verstehen.\\
In Abbildung \ref{fig:gzip_source} ist die Struktur des GZIP Projekts dargestellt. Es ist zu erkennen, dass GZIP aus zwölf C-Dateien und sechs Header Dateien besteht. Innerhalb dieser Dateien bestehen viele Abhängigkeiten und Funktionen unterschiedlicher Dateien rufen sich gegenseitig auf. Des Weiteren wird oft auf globale Variablen anderer Dateien zugegriffen. Zusätzlich erschwert die Schreibweise gelegentlich das Verständnis. So werden Funktionen als lokale Pointer deklariert um später einen kürzeren Aufrufbefehl verwenden zu können. Auch eine ausführliche Dokumentation gibt es nicht, somit bleiben nur die Kommentare im Code und der Programmcode selber um die Funktionsweise und den Ablauf nachzuvollziehen.\\
\newline
GZIP startet in \textit{gzip.c}. Dort werden die Startparameter verarbeitet und entsprechende Einstellungen vorgenommen. Falls mehrere Dateien oder ein Ordner zum Komprimieren übergeben wird, ist in dieser Datei die Schleife, in der die einzelnen Dateien durchlaufen werden (siehe Algorithmus \ref{alg:gzip_seq}). Von dort wird die zip-Funktion in \textit{zip.c} aufgerufen, wo unterschiedlichste Buffer initialisiert und die deflate-Methode in \textit{deflate.c} aufgerufen. Wie der Name der Funktion schon vermuten lässt, findet in dieser Methode die eigentliche Komprimierung statt und die komprimierten Daten werden an den Output Stream weitergegeben. Hier ist somit die Stelle, an der angesetzt werden muss um den Algorithmus zu parallelisieren.\\
\newline
Die Datei \textit{deflate.c} beinhaltet fünf Funktionen:
\begin{enumerate}[leftmargin=2cm]
    \item \textit{\textbf{void} lm\_init (pack\_level, flags)}
    \item \textit{\textbf{void} fill\_window()}
    \item \textit{\textbf{int} longest\_match(cur\_match)}
    \item \textit{\textbf{unsigned long} deflate()}
    \item \textit{\textbf{unsigned long} deflate\_fast()}
\end{enumerate}
Dabei wird \textit{lm\_init (pack\_level, flags)} und \textit{deflate()} aus der zip-Methode aufgerufen. \textit{lm\_init (pack\_level, flags)} hat zwei Input Parameter. Der erste, \textit{pack\_level}, definiert das Komprimierungslevel. Er kann zwischen Null und Neun liegen, wobei Null die Daten einfach eins zu eins speichert und Neun die höchste Komprimierungsstufe darstellt. Der zweite Parameter, flags, ist ein Zeiger auf Konfigurationseinstellungen, die für das Komprimieren benötigt werden. \textit{lm\_init} initialisiert somit einige Ablaufparameter und initialisiert die Hash Map, die für die Vergleiche verwendet wird, und das Fenster, das später über den Input Stream geschoben wird.\\
Durch das Aufrufen von \textit{deflate()} wird mit der eigentlichen Komprimierung begonnen. Als erstes wird das gewünschte Komprimierungslevel überprüft. Ist dieses zwischen Null und Drei, wird \textit{deflate\_fast()} aufgerufen. Diese Methode komprimiert den Input Stream schneller, jedoch mit einem geringeren Komprimierungsfaktor. Im Prinzip wird hier das Fenster etwas ungenauer nach Übereinstimmungen (Matches) durchsucht, bzw. geringere Match-Längen akzeptiert. Sollte das Komprimierungslevel größer als Drei sein, so wird eine Schleife durchlaufen, bis das Ende der Datei erreicht ist. In jedem Schleifendurchlauf wird die \textit{longest\_match} Methode aufgerufen. Dieser Methode wird ein Zeiger auf den letzen Match übergeben. Wird ein besserer Match gefunden, so wird die Länge des neuen Matches als Rückgabewert übergeben, ansonsten die Länge des alten. \textit{longest\_match} vergleicht im Standardfall immer zwei Bytes auf einmal, um eine höhere Effektivität und Geschwindigkeit zu erreichen. Beim Aufruf von \textit{longest\_match} können zwei Fälle eintreten:
\begin{enumerate}[leftmargin=2cm]
    \item Es ist der erste Aufruf und somit ist noch kein vorheriger Match vorhanden. In diesem Fall wird begonnen das Fenster zu durchsuchen, bis eine Überein-stimmung gefunden wurde, die \grqq gut genug\grqq ist.
    \item Es ist bereits ein vorheriger Match vorhanden. In diesem Fall wird das Fenster so lange weiter durchsucht, bis ein besserer Match als der vorherige gefunden wird. Wird kein besserer gefunden, so wird die Länge des letzten Matches zurück gegeben. Andernfalls die des neuen Matches. 
\end{enumerate}
\textit{deflate()} ruft dann Methoden zur Speicherung des Matches im Huffman Baum auf und schreibt ggf. in den Output Stream. Weiterhin wird nach jeden Schleifendurchlauf das Fenster weiter geschoben.\\
Dies übernimmt \textit{fill\_window()}. Im Grunde die einzige Aufgabe dieser Funktion ist das korrekte verschieben des Fensters, dabei wird darauf geachtet, dass das Fenster nicht zu weit und nicht zu kurz verschoben wird. Weiterhin ist wichtig, dass hierbei die Länge des Fensters nicht verändert wird. Die einzige Ausnahme bildet hier das Ende der Datei. Natürlich darf in diesem Fall das Fenster nicht über das Ende der Datei hinaus verschoben werden, es muss also ggf. verkleinert werden. \textit{fill\_window()} setz beim Durchlauf die End-Of-File Variable um der \textit{deflate()} Methode zu signalisieren, dass keine weiteren Daten vorhanden sind und die Methode beendet werden kann.\\
\newline
Wie an den Methodenköpfen zu erkennen ist, werden nur sehr wenige Informationen über Parameter ausgetauscht. Dies ist prinzipiell eher schlecht wenn man ein Programm parallelisieren möchte, da hier vermehrt mit globalen Variablen und Buffern gearbeitet wird. Das größte Problem ist somit erstmal das Eliminieren globaler Variablen und die Übergabe der Informationen als Parameter.\\
Da \textit{deflate()} als Einstiegspunkt der \textit{zip} Funktion dient, sollte dieser Methodenkopf sich im besten Fall nicht ändern. Daher wurde eine zusätzliche Funktion eingeführt: \textit{deflate\_part}. Sie beinhaltet zum größten Teil den ursprünglichen Code aus \textit{deflate()}. Die \textit{deflate()} Methode wird zukünftig verwendet um den Input Stream in Blöcke zu zerteile, die entsprechenden Indizes zu berechnen, die Threads zu erstellen und zu starten und die benötigten Informationen an die \textit{defalte\_part} Methode zu übergeben.\\
Wie bereits erwähnt, wurde \textit{fill\_window()} aus der ursprünglichen \textit{deflate()} Methode aufgerufen. Da zukünftig jedoch kein verschieben des Fensters mehr vorgenommen werden soll, fällt diese Methode weg. Vor jedem Aufruf von \textit{deflate\_part} werden alle Buffer neu initialisiert und dann entsprechend an die Methode übergeben. In den folgenden zwei Listings werden die unterschiede zwischen dem orginal Aufruf von \textit{deflate} und \textit{deflate\_part} veranschaulicht.\\

\begin{lstlisting}[caption={Original Methodenkopf der deflate Methode}, label=alg:deflate]
ulg deflate(){
\end{lstlisting}
$\;$ \\
\begin{lstlisting}[caption=Veränderter Methodenkopf der deflate\_part Methode, label=alg:deflate_part]
ulg deflate_part(look_ahead, str_start, window, eo_file, blockstart, header, prev, ins_h)
	unsigned look_ahead;
	unsigned str_start;
	uch *window;
	int eo_file;
	long blockstart;
	uch *header;
	ush *prev;
	unsigned ins_h; {
\end{lstlisting}
$\;$ \\
Der Unterschied ist klar erkennbar, obwohl beide Methoden grundsätzlich das Selbe tun, werden im Listing \ref{alg:deflate_part} deutlich mehr Parameter verwendet als bei Listing \ref{alg:deflate}. Dies ist nötig um eine unabhängige Ausführung von \textit{deflate\_part} zu ermöglichen. Von vorne beginnend werden folgende Parameter übergeben: der Endeindex (look\_ahead), der Startindex(str\_sart), ein Zeiger auf den Block (window), ein Marker der anzeigt ob es sich um das Ende der Datei handelt (eo\_file), ein Zeiger auf die Hash Map (header), ein Zeiger auf das Array mit den vorherigen Matches (prev) und ein Index für die Hash Map (ins\_h).\\
Um nun diese Methode mit Hilfe von \textit{pthread} parallelisieren zu können, muss die Anzahl der Parameter auf einen reduziert werden. Dies wurde mittels einer Struktur erreicht. Diese Struktur entspricht, wenig überraschend, genau den in Listing \ref{alg:deflate_part} aufgeführten Parametern. 
%
%In Listing \ref{alg:deflate_part_parallel} ist nun die neue Struktur und der sich daraus ergebene Methodenkopf aufgelistet.\\
%
%\begin{lstlisting}[caption=Parallelisierter Methodenkopf der deflate\_part Methode, label=alg:deflate_part_parallel]
%struct DefalteData{
%    unsigned look_ahead;
%    unsigned str_start;
%    int max_lazy_match;
%    uch *window;
%    int eo_file;
%    long blockstart;
%    uch *header;
%    ush *prev;
%    unsigned ins_h;
%};
%
%ulg deflate_part(defalte_data)
%    struct DefalteDate deflate_data; {
%\end{lstlisting} 
$\;$ \\
\textit{deflate\_part} und die entsprechenden Daten können nun an die \textit{pthread\_create} Methode übergeben und folglich parallel bearbeitet werden. Listing \ref{alg:deflate_part_pthread} zeigt diesen Aufruf.\\
\begin{lstlisting}[caption=POSIX Thread für deflate\_part, label=alg:deflate_part_pthread]
#include <pthread.h>
...
  struct data{
   	unsigned look_ahead;
	unsigned str_start;
	uch *window;
	int eo_file;
	long blockstart;
	uch *header;
	ush *prev;
	unsigned ins_h;
  };
  pthread_create(&thread[i], NULL, deflate_part, &data[i]);
...
\end{lstlisting} 
$\;$ \\
Obwohl die drei letzten Listings eventuell den Eindruck vermitteln könnten, dass die Umstellung des seriellen LZ77 Algorithmus und der Huffman Kodierung auf eine parallele Verarbeitung relativ einfach wäre, entspricht dies jedoch nicht der Wirklichkeit. Die Umstellung bedarf einer erheblichen Einarbeitungszeit und führte bisher, trotz komplexer Änderungen, nicht zum erhofften Ergebnis. Dies wird jedoch im Fazit genauer ausgeführt.\\
Weiteres konnte der LZ77 Algorithmus selber zwar parallelisiert werden, jedoch ist die weitere Verarbeitung, also das Generieren der Huffman Bäume und das Speichern der komprimierten Daten in einer Datei weiterhin seriell. Um diese Umsetzung auch noch zu realisieren fehlte angesichts des begrenzten Zeitraums für die Seminararbeit die Zeit und vermutlich auch etwas das benötigte Knowhow.

\clearpage